The invention relates generally to signal encoding and more particularly to a technique for encoding data for storage on a magnetic medium such as a computer disk.
The operating speeds of peripheral computer components such as disk drives often prevent computer engineers from designing faster computer systems. The speeds of microprocessors, which are at the hearts of today""s computer systems, have increased dramatically within the last few years. But the speeds of today""s disk drives and semiconductor memory circuits have lagged behind. Therefore, these slower peripheral components typically limit the overall speed of a computer system because the system microprocessor must effectively xe2x80x9cslow downxe2x80x9d to transfer data to and from these components. That is, these slower components are the xe2x80x9cweak link in the chainxe2x80x9d. Fortunately, the new RAMBUS(copyright) architecture promises to make the next generation of semiconductor memory circuits as fast or faster than the next generation of microprocessors. But, there have been no speed-increasing breakthroughs of this magnitude in disk-drive technology.
Unfortunately, conventional data-encoding techniques can further reduce the already slow data-transfer rates of many disk drives. For example, many data codes are relatively inefficient, i.e., use a relatively large number of code bits per data bit, and thus may significantly reduce the effective writing speed of a disk drive. Furthermore, many data codes are poorly designed, and thus may significantly reduce the effective reading speed of a disk drive. Specifically, if the system processor initially detects a read error, then it tries to correct the error using conventional error-correction techniques. If the processor cannot correct the error using these techniques, then it instructs the disk drive to re-read the data. Unfortunately, error detection, error correction, and data re-read are time-consuming actions that can significantly reduce the effective reading speed of a disk drive.
FIG. 1 is a block diagram of a conventional disk-drive write channel 10, which includes an encoder 12 for encoding data into a Non-Return-To-Zero-Interleave (NRZI) sequence of conventional Run-Length-Limited (RLL) code words. The write channel 10 also includes a pre-coder 14 for converting this NRZI sequence of code words into a corresponding Non-Return-To-Zero (NRZ) sequence of code words. A write-head driver circuit 16 provides the NRZ sequence of code words to a write head 18, which writes the code words onto a magnetic storage medium 20 such as a hard disk.
Unfortunately, conventional RLL coding techniques often limit the speed at which the channel 10 can write data to the medium 20, and thus limit the data-write speed of the disk drive containing the channel 10 and the medium 20. As discussed below in conjunction with FIGS. 3 and 4, an RLL code word is often relatively inefficient, and this inefficiency limits the effective speed at which the channel 10 can write data to the medium 20. Therefore, it is difficult if not impossible to realize significant increases in data-write speeds using conventional RLL coding techniques.
FIG. 2 is a block diagram of a conventional read channel 22, which reads the NRZ sequence of RLL code words that the write channel 10 (FIG. 1) wrote to the storage medium 20. The read channel 22 includes a read head 24 for reading the code words stored on the medium 20 and for generating a corresponding read signal. A read circuit 26 amplifies the read signal, and a Viterbi detector 28 recovers the NRZ sequence of RLL code words from the read signal. A post-coder 30 converts the recovered NRZ sequence into the corresponding NRZI sequence, and a decoder 32 decodes the NRZI sequence into the read data. Assuming there are no read errors, the recovered NRZ sequence, NRZI sequence, and read data are respectively the same as the NRZ sequence generated by the pre-coder 14, the NRZI sequence generated by the encoder 12, and the write data provided to the encoder 12 (FIG. 1). Therefore, the read channel 22 is effectively the inverse of the write channel 10.
Unfortunately, conventional RLL coding techniques often limit the speed at which the channel 22 can read data from the medium 20, and thus limit the data-read speed of the disk drive containing the channel 22 and the medium 20. As discussed above in conjunction with FIG. 1, an RLL code word is relatively inefficient, and this inefficiency limits the effective speed at which the channel 22 can read data from the medium 20. Furthermore, as discussed below in conjunction with FIGS. 3 and 4, an RLL code word may significantly degrade the signal-to-noise ratio (SNR) of the data-read signal. Unfortunately, this inefficiency and the degraded SNR limit the effective speed at which the channel 22 can read data from the medium 20. Therefore, it is difficult if not impossible to realize significant increases in data-read speed using conventional RLL coding techniques.
In conjunction with FIGS. 3-10, a general discussion of conventional data read/write and encoding techniques is included to assist the reader in understanding the subsequently discussed inventive concepts. Numerous detailed discussions of these conventional techniques are included in available references such as xe2x80x9cDigital Baseband Transmissionxe2x80x9d by Jan W. Bergmans.
Referring to FIGS. 3 and 4, conventional RLL encoding techniques and code words are discussed. Generally, RLL code words are stored on a computer disk instead of data words because the code words can be selected to have desirable parameters that the data words will not always have. As discussed below, the read channel 22 (FIG. 2) depends on these parameters for proper operation.
FIG. 3 is a data word 40 and its equivalent RLL code word 42. The word 40 includes data bits D0-Da, and the code word 42 includes code bits C0-Cb and is compatible with an x/y RLL (d/k) code. The parameter x/y is the efficiency of the RLL code, and indicates that the code word 42 encodes x=a+1 data bits with y=b+1 code bits. Therefore, the higher the ratio x/y, the fewer the number of code bits that are written and read for each data bit, and thus the faster the data-write and data-read speeds for a given number of data bits. Conversely, the lower the ratio x/y, the greater the number of code bits that are written and read for each data bit, and thus the slower the data-write and data-read speeds for a given number of data bits. The parameter d is the minimum number of code bits C required between consecutive code-bit transitions, and the parameter k is the maximum number of code bits C allowed between consecutive code-bit transitions. For example, binary code sequences 01 and 10 include 0-to-1 and 1-to-0 code-bit transitions, respectively, and an x/y RLL (0/7) code may include the binary sequence 101000000001, which respectively includes 0 bits (minimum) and 7 bits (maximum) between consecutive code-bit transitions. The Viterbi detector 28 (FIG. 1) includes a state machine having a structure based on the responses of the portion of the read channel 22 that includes the read head 24 and read circuit 26, and possibly on the state sequence of the code if such a state sequence exists. Furthermore, the detector 28 or a separate clock detector (not shown) uses the code-bit transitions to synchronize a read clock signal for sampling the read signal from the read head 24.
FIG. 4 shows the first three code words 42a, 42b, and 42c of a code sequence 44, which is compatible with an 8/9 RLL (0/7) code. Because d=0, there need be no code bits between code-bit transitions. That is, the sequence 44 can have consecutive code-bit transitions such as in the binary series 010101. To insure that the sequence 44 never has more than k=7 code bits between consecutive code-bit transitions, each code word 42a-42c is selected to have at least one respective transition within one or more predefined code-word sections. For example, having at least one transition in both of the code-word sections 46a-46c (C0-C3) and 48a-48c (C6-C8) of each respective code word 42a-42c guarantees that the sequence 44 never has more than 7 bits between consecutive code-bit transitions.
Unfortunately, because they are typically designed to have relatively small error propagations, RLL codes are often relatively inefficient. As discussed above, such inefficiency reduces the data-transfer speeds of the write and read channels 10 and 22 (FIGS. 1 and 2 ). For example, an 8/9 RLL code word represents 8 bits (a byte) of data. If there is an error in the 9-bit code word, then there is a read error in at most one byte of data. If there is an error that crosses the boundary between two consecutive 8/9 code words, then there is a read error in at most two bytes of data. Thus, the error propagation of the 8/9 RLL code is somewhere between 1 and 2 bytes. On the other hand, because a 16/17 code word represents 2 bytes of data, a code-word error can cause read errors in up to 2 bytes of data, and a cross-boundary error can cause read errors in up to 4 bytes of data. Thus, the error propagation of the 16/17 RLL code is approximately twice that of the 8/9 RLL code. Therefore, even though an RLL code having short code words is typically more inefficient than an RLL code having longer code words, the short-word RLL code is often preferred because it has a smaller error propagation.
Furthermore, because RLL codes are typically designed to reduce the occurrence of a specific type of read error, RLL code sequences often have relatively large numbers of bit transitions. This relatively high rate of bit transitions typically lowers the SNR of the read signal, and thus typically reduces the accuracy and effective speed of the read channel 22 (FIG. 2). For example, a Maximum-Transition-Rate (MTR) code is a popular RLL code that is designed to eliminate or reduce the occurrence of tri-bit read errors, which are three consecutive erroneous code bits. Tri-bit errors typically occur in three-bit sequences that have two bit transitions, such as 101 being erroneously read as 010. Therefore, MTR codes are typically structured to avoid long sequences of consecutive code-bit transitions. Unfortunately, MTR codes can do very little to increase accuracy if a significant number of the errors are not tri-bit errors.
Referring to FIGS. 5-8, NRZI and NRZ sequences are discussed. As discussed below, the combination of the NRZI-to-NRZ conversion in the write channel 10 (FIG. 1) and the NRZ-to-NRZI conversion in the read channel 22 (FIG. 2) prevents reverse connection of the write head 18 or the read head 24 from causing data errors. Typically, the write head 18 and the read head 24 each have two connection terminals. The polarities of the heads 18 and 24 depend on how these terminals are connected to the write circuit 16 and the read circuit 26, respectively. For example, if connected to have a positive polarity, the write head 18 does not invert the code bits from the circuit 16, and thus writes a logic 0 from the circuit 16 as a logic 0 and writes a logic 1 from the circuit 16 as a logic 1. Conversely, if connected to have a negative polarity, the write head 18 inverts the code bits from the circuit 16, and thus writes a logic 0 from the circuit 16 as a logic 1 and writes a logic 1 from the circuit 16 as a logic 0. A similar analysis can be made for the read head 24. Therefore, if both the write and read heads 18 and 24 are connected to have the same polarity (either positive or negative), then the read data generated by the read channel 22 has the same polarity as the write data input to the write channel 10. But if the write and read heads 18 and 24 are connected to have different polarities, then the read data has the opposite polarity from the write data, and thus a catastrophic read error occurs. Unfortunately, today""s manufacturing techniques make such reverse-polarity head connections relatively common. Therefore, as discussed below in conjunction with FIGS. 7 and 8, a NRZI-NRZ-NRZI conversion is used because it cancels out such head-polarity errors.
FIG. 5 is a schematic diagram of the pre-coder 14 (FIG. 1), which converts a NRZI sequence into a NRZ sequence. The pre-coder 14 includes an XOR gate 50, which receives the NRZI sequence of bits on an input terminal 52 and provides a corresponding NRZ sequence of bits on an output terminal 54. The pre-coder 14 also includes a first-order delay 56 connected between an input terminal 58 and the output terminal 54 of the XOR gate 50. Therefore:
NRZoutT=NRZlinT⊕NRZoutTxe2x88x921xe2x80x83xe2x80x83(1)
where ⊕ is the mathematical symbol for the XOR operation and T represents a discrete point in time.
In operation, any sequence of bitsxe2x80x94such as the sequence from the encoder 12 (FIG. 1)xe2x80x94can be arbitrarily labeled as a NRZI sequence, and the pre-coder 14 converts this sequence into a corresponding NRZ sequence of bits.
FIG. 6 is a schematic diagram of the post-coder 30 (FIG. 2), which converts a NRZ sequence into a NRZI sequence. The post-coder 30 includes an XOR gate 60, which receives the NRZ sequence of bits on an input terminal 62 and provides the corresponding NRZI sequence of bits on an output terminal 64. The post-coder 30 also includes a first-order delay 66 connected between the input terminal 62 and another input terminal 68. Therefore:
NRZIoutT=NRZinT⊕NRZinTxe2x88x921xe2x80x83xe2x80x83(2)
In operation, any sequence of bitsxe2x80x94such as the sequence from the Viterbi detector 28 (FIG. 2)xe2x80x94can be arbitrarily labeled as a NRZ sequence, and the post-coder 30 converts this sequence into a corresponding NRZI sequence of bits. As discussed below in conjunction with FIGS. 7 and 8, if the output terminal 54 of the pre-coder 14 (FIG. 5) is coupled to the input terminal 62 of the post-coder 30, then NRZIinT=NRZIoutT.
FIG. 7 is an example of a NRZI-NRZ-NRZI conversion using the pre-coder 14 (FIG. 5) and the post-coder 30 (FIG. 6). Assume a binary NRZI sequence of 010110 and that NRZTTxe2x88x921 (the output of the delay 56 at time Txe2x88x921)=0. First, the pre-coder 14 performs the NRZI-to-NRZ portion of the conversion starting with the first bit (the right-most bit in this example) of the NRZI sequence and ending with the last bit (the left-most bit in this example) of the NRZI sequence. Therefore, the resulting NRZ sequence is 1100100, which includes NRZTxe2x88x921 as the first bit. By staggering the NRZ sequence such that its bits are between the bits of the NRZI sequence, one can see that the NRZI sequence is the derivative of the NRZ sequence. That is, wherever NRZIT=1, a transition occurs between the corresponding bits of the NRZ sequence. Conversely, wherever NRZIT=0, no transition occurs between the corresponding bits of the NRZ sequence. For example, the second bit (from the right) of the NRZI sequence is logic 1, and the second and third bits of the NRZ sequence are logic 0 and logic 1, respectively. Thus, NRZIT+1=logic 1 indicates that there is a transition between NRZT and NRZT+1. Similarly, the fourth bit of the NRZI sequence is logic 0, and the fourth and fifth bits of the NRZ sequence are logic 0. Thus, NRZIT+3=logic 0 indicates that there is no transition between NRZT+2 and NRZT+3. Next, the post-coder 30 performs the NRZ-to-NRZI portion of the conversion starting with the first (right-most) bit of the NRZ sequence and ending with the last (left-most) bit. Therefore, the resulting NRZI sequence is 010110, which is the same NRZI sequence we started with.
FIG. 8 illustrates the ability of the NRZI-NRZ-NRZI conversion to cancel negative head polarities. For example, if either the write head 18 (FIG. 1) or the read head 24 (FIG. 2)xe2x80x94but not bothxe2x80x94is connected to have a negative polarity, then the Viterbi detector 28 (FIG. 2) generates {overscore (NRZ)}. But despite this inversion, the post-coder 30 recovers the original NRZI sequence 010110.
Referring to FIG. 9, parity is a technique used to detect errors in uncoded data. For example, before a binary data byte D is transmitted, it is assigned a parity bit P whose value depends on the values of the bits D0-D7. The combination of D and P forms a 9-bit parity word 72. For even parity, the value of P is such that the total number of xe2x80x9c1""sxe2x80x9d in the word 72 is even. Therefore, if the number of xe2x80x9c1""sxe2x80x9d in D is odd, then P=1. Likewise, if the number of xe2x80x9c1""sxe2x80x9d in D is even, then P=0. For odd parity, the value of P is such that the total number of xe2x80x9c1""sxe2x80x9d in the word 72 is odd. Therefore, if the number of xe2x80x9c1""sxe2x80x9d in D is odd, then P=0. Likewise, if the number of xe2x80x9c1""sxe2x80x9d in D is even, then P=1. For example, if D=10101010, then there are four xe2x80x9c1""sxe2x80x9d in D. Therefore, P=0 for even parity and P=1 for odd parity. Similarly, if D=10101011, then there are five xe2x80x9c1""sxe2x80x9d in D. Therefore, P=1 for even parity and P=0 for odd parity. The word 72 is then transmitted to a decoder (not shown) that checks the parity of the word 72. If the parity is incorrect, then the decoder identifies the word 72 as including an error. One may then attempt to recover the correct value of D using conventional error-correction techniques.
Although parity is widely used for error detection in uncoded data, it is rarely, if ever, used for error detection in RLL coded data.
In one aspect of the invention, a code word includes a first group of data bits and includes code bits that represent a second group of data bits. In another aspect of the invention, there is a minimum probability of bit transitions among the code bits. In yet another aspect of the invention, the code word includes a parity bit.
Unlike conventional codes, a code that includes such a code word can have both a high efficiency and a small error propagation. Additionally, by including fewer bit transitions, a sequence of such code words causes less read noise, and thus causes fewer read errors as compared to sequences of known code words. Moreover, such a code word can include a parity bit to allow improved error detection as compared to known error-detection techniques for coded data.